/*
 * @lc app=leetcode.cn id=109 lang=cpp
 *
 * [109] 有序链表转换二叉搜索树
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    vector<ListNode *> vec;

    TreeNode *divide(int l, int r)
    {
        if (l == r)
        {
            return new TreeNode(vec[l]->val);
        }
        if (l > r)
            return nullptr;

        int mid = l + (r - l) / 2;
        TreeNode *root = new TreeNode(vec[mid]->val);
        if (mid > l)
        {
            root->left = divide(l, mid - 1);
        }
        if (mid < r)
        {
            root->right = divide(mid + 1, r);
        }
        return root;
    }

    TreeNode *sortedListToBST(ListNode *head)
    {
        if (!head)
            return nullptr;
        while (head)
        {
            vec.push_back(head);
            head = head->next;
        }


        return divide(0, vec.size() - 1);
    }
};
// @lc code=end
